package club.vann.leetcode.race;

/**
 * <p>难度：Medium</p>
 * <p>题目：找出星型图的中心节点</p>
 * <p>描述：有一个无向的 星型 图，由 n 个编号从 1 到 n 的节点组成。星型图有一个 中心 节点，并且恰有 n - 1 条边将中心节点与其他每个节点连接起来。
 *
 * 给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间存在一条边。请你找出并返回 edges 所表示星型图的中心节点。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：edges = [[1,2],[2,3],[4,2]]
 * 输出：2
 * 解释：如上图所示，节点 2 与其他每个节点都相连，所以节点 2 是中心节点。
 * 示例 2：
 *
 * 输入：edges = [[1,2],[5,1],[1,3],[1,4]]
 * 输出：1
 *
 *
 * 提示：
 *
 * 3 <= n <= 105
 * edges.length == n - 1
 * edges[i].length == 2
 * 1 <= ui, vi <= n
 * ui != vi
 * 题目数据给出的 edges 表示一个有效的星型图</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-03-14:10:58:19
 */
public class LeetCode_5702 {
    public static void main(String[] args) {
        LeetCode_5702 leetCode = new LeetCode_5702();

        System.out.println("Result["+TestCase.ANS+"] : " + leetCode.findCenter(TestCase.EDGES));
        System.out.println("Result["+TestCase.ANS1+"] : " + leetCode.findCenter(TestCase.EDGES1));
    }

    /**
     * 解法一：
     *
     * @param edges
     * @return
     */
    public int findCenter(int[][] edges) {
        // n 条边
        int n = edges.length;
        // n+1 个节点
        int[] edge = new int[n+2];

        int ans = 0;
        for(int[] arr : edges) {
            edge[arr[0]] ++;
            edge[arr[1]] ++;

            if(edge[arr[0]] == n) {
                ans = arr[0];
            }
            if(edge[arr[1]] == n) {
                ans = arr[1];
            }
        }

        return ans;
    }

    static class TestCase {
        public static int ANS = 2;
        public static int[][] EDGES = {{1, 2}, {2, 3}, {4, 2}};

        public static int ANS1 = 1;
        public static int[][] EDGES1 = {{1, 2}, {5, 1}, {1, 3}, {1, 4}};
    }
}
